package lru

import (
	"container/list"
)

type Cache struct {
	maxBytes int64  // 允许使用的最大内存
	nBytes int64    // 当前已使用的内存
	ll *list.List  // 标准库的双向链表
	cache map[string]*list.Element  // 键是字符串，值是双向链表中对应节点的指针
	OnEvicted func(key string, value Value)  // 某条记录被移除时的回调函数，可以为nil
}

// 双向链表节点的数据类型，在链表中保存每个值对应的Key作用在于，
type entry struct {
	key string
	value Value
}

type Value interface {
	Len() int
}

// 实例化Cache
func New(maxBytes int64, onEvicted func(string, Value)) *Cache{
	return &Cache{
		maxBytes:  maxBytes,
		ll:        list.New(),
		cache:     make(map[string]*list.Element),
		OnEvicted: onEvicted,
	}
}

// 通过key查询value
func (c *Cache) Get(key string) (value Value, ok bool){
	// 如果键对应的链表节点存在
	if ele, ok := c.cache[key]; ok{
		c.ll.MoveToFront(ele)  // 将链表节点移动到队尾 (双向链表的队首队尾是相对的，这里约定front为队尾)
		kv := ele.Value.(*entry)
		return kv.value, true
	}
	return
}

// 缓存淘汰，即移除最近最少访问的节点（队首）
func (c *Cache) RemoveOldest(){
	ele := c.ll.Back()  // 返回最后的一个ele
	if ele != nil{
		c.ll.Remove(ele)  // 移除该ele
		kv := ele.Value.(*entry)  // 获取该ele中的Value，并断言为类型 *entry
		delete(c.cache, kv.key)   // 删除map中的key
		c.nBytes -= int64(len(kv.key)) + int64(kv.value.Len())  // 更新当前使用的内存数
		if c.OnEvicted != nil{
			c.OnEvicted(kv.key, kv.value)  // 调用移除时的回调
		}
	}
}

// 新增
func (c *Cache) Add(key string, value Value){
	if ele, ok := c.cache[key]; ok{
		c.ll.MoveToFront(ele)  // 如何该节点已存，则将其移到队尾
		kv := ele.Value.(*entry)
		c.nBytes += int64(value.Len()) - int64(kv.value.Len())
		kv.value = value
	}else{
		ele := c.ll.PushFront(&entry{key,value})  // 如果节点不存在，则插入新节点
		c.cache[key] = ele  // 在字典中添加key与节点的映射关系
		c.nBytes += int64(len(key)) + int64(value.Len())
	}

	// 如果内存超过最大值，则移除最近最少使用的节点
	if c.maxBytes != 0 && c.maxBytes < c.nBytes{
		c.RemoveOldest()
	}

}

//
func (c *Cache) Len() int{
	return c.ll.Len()
}











